package week06

// 198. 打家劫舍
// https://leetcode-cn.com/problems/house-robber/

func rob(nums []int) int {
	var dp = make([][]int, 2)
	for i := range dp {
		// 金额不可能是负数，不需要初始化math.MinInt32
		dp[i] = make([]int, 2)
	}
	// j：0-不偷  1-偷
	for i := 1; i <= len(nums); i++ {
		for j := 0; j <= 1; j++ {
			dp[i&1][j] = max(dp[i&1][j], dp[(i-1)&1][j])
			if j == 0 {
				dp[i&1][0] = max(dp[i&1][0], dp[(i-1)&1][1])
			} else {
				dp[i&1][1] = max(dp[i&1][1], dp[(i-1)&1][0] + nums[i-1])
			}
		}
	}
	return max(dp[len(nums)&1][0], dp[len(nums)&1][1])
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}